package com.example.demo.algorithm.sort.fast_sort;

/**
 *  快速排序的时间复杂度为O(NlogN).
 * @author: htc
 * @date: Created in 11:31 2019/2/21.
 */
public class Demo2 {

    static int[] arr = {12, 20, 5, 16, 15, 1, 30, 45, 23, 9};

    public static int partition(int[] array, int lo, int hi) {
        //固定的切分方式
        int key = array[lo];
        while (lo < hi) {
            //从后半部分向前扫描
            while (array[hi] >= key && hi > lo) {
                hi--;
            }
            array[lo] = array[hi];

            //从前半部分向后扫描
            while (array[lo] <= key && hi > lo) {
                lo++;
            }
            array[hi] = array[lo];
        }
        array[hi] = key;
        return hi;
    }

    public static void sort(int[] array, int lo, int hi) {
        if (lo >= hi) {
            return;
        }
        int index = partition(array, lo, hi);
        sort(array, lo, index - 1);
        sort(array, index + 1, hi);
    }

    public static void main(String[] args) {
        sort(arr, 0, arr.length - 1);
       for (int i: arr){
           System.out.print(i+" ");
       }
    }
}
